package one.three.thirtySix;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

public class RandomQueue<Item> implements Iterable<Item> {
	private Item[] a;
	private int h;
	private int t;
	private int n;
	private static int initialSize = 4;

	public boolean isEmpty() {
		return n == 0;
	}

	public int size() {
		return n;
	}

	private void resize(int s) {
		Item[] temp = (Item[]) new Object[s];
		if (s > a.length) {
			if (h <= t) {
				for (int i = 0; i < a.length; i++) {
					temp[i] = a[i];
				}
			} else {
				for (int i = h; i < a.length; i++) {
					temp[i - h] = a[i];
				}
				for (int i = 0; i <= t; i++) {
					temp[i + a.length - h] = a[i];
				}
				h = 0;
				t = n - 1;
			}
		} else {
			if (h <= t) {

				for (int i = h; i <= t; i++) {
					temp[i - h] = a[i];
				}
				h = 0;
				t = n - 1;
			} else {
				for (int i = h; i < a.length; i++) {
					temp[i - h] = a[i];
				}
				for (int i = 0; i <= t; i++) {
					temp[i + a.length - h] = a[i];
				}
				h = 0;
				t = n - 1;
			}

		}
		a = temp;
	}

	public void enqueue(Item item) {
		pushHead(item);
	}

	public void pushHead(Item item) {
		if (a == null) {
			a = (Item[]) new Object[initialSize];
			a[0] = item;
			n++;
			h = 0;
			t = 0;
		} else {
			int newH = h - 1;
			if (newH < 0)
				newH += a.length;
			a[newH] = item;
			h = newH;
			n++;
			if (n > a.length / 2)
				resize(a.length * 2);
		}
	}

	public void pushTail(Item item) {
		if (a == null) {
			a = (Item[]) new Object[initialSize];
			a[0] = item;
			n++;
			h = 0;
			t = 0;
		} else {
			int newT = t + 1;
			if (newT >= a.length)
				newT -= a.length;
			a[newT] = item;
			t = newT;
			n++;
			if (n > a.length / 2)
				resize(a.length * 2);
		}
	}

	public Item popHead() {
		if (a != null) {
			Item item = a[h];
			h++;
			if (h >= a.length) {
				h -= a.length;
			}
			n--;
			if (n < a.length / 4 && n > initialSize)
				resize(a.length / 2);

			return item;
		} else {
			return null;
		}
	}

	private void changeLast() {
		if (h == t) {

		} else if (h < t) {
			int id = randomInt(h, t - 1);
			Item tmp = a[id];
			a[id] = a[t];
			a[t] = tmp;
		} else {
			int id1 = randomInt(h, a.length - 1);
			int id2 = randomInt(0, t - 1);
			int id = new Random().nextBoolean() ? id1 : id2;
			Item tmp = a[id];
			a[id] = a[t];
			a[t] = tmp;
		}
	}

	private static int randomInt(int min, int max) {
		int r = new Random().nextInt(max - min + 1);
		return r + min;
	}

	public Item popTail() {
		if (a != null) {
			Item item = a[t];
			t--;
			if (t < 0) {
				h += a.length;
			}
			n--;
			if (n < a.length / 4 && n > initialSize)
				resize(a.length / 2);

			return item;
		} else {
			return null;
		}
	}

	public Item dequeue() {
		changeLast();
		Item r = popTail();
		return r;
	}

	public Item sample() {
		changeLast();
		Item r = a[t];
		return r;
	}

	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		if (a != null) {
			if (h <= t) {
				for (int i = h; i <= t; i++) {
					s.append("[" + a[i] + "]");
				}
			} else {
				for (int i = h; i < a.length; i++) {
					s.append("[" + a[i] + "]");
				}
				for (int i = 0; i <= t; i++) {
					s.append("[" + a[i] + "]");
				}
			}
		}
		return s.toString();
	}

	public void showA() {
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}

	private static int randomIndex(int min, int max, List<Integer> e) {
		int r = -1;
		Random random = new Random();
		do {
			r = random.nextInt(max + 1 - min);
		} while (e.contains(r + min));
		return r + min;
	}

	private Item[] shuffle(Item[] o) {
		int[] ind = new int[n];
		int idx = -1;
		List<Integer> l = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			idx = randomIndex(0, n - 1, l);
			ind[i] = idx;
			l.add(idx);
		}
		Item[] r = (Item[]) new Object[n];
		for (int i = 0; i < n; i++) {
			r[i] = o[ind[i]];
		}
		return r;
	}

	@Override
	public Iterator<Item> iterator() {
		return new RandomQueueIterator();
	}

	private class RandomQueueIterator implements Iterator<Item> {

		private Item[] r;
		private int i;

		public RandomQueueIterator() {
			r = (Item[]) new Object[n];
			i = 0;
			if (h <= t) {
				for (int i = h; i <= t; i++) {
					r[i] = a[i];
				}
			} else {
				for (int i = h; i < a.length; i++) {
					r[i - h] = a[i];
				}
				for (int i = 0; i <= t; i++) {
					r[i + a.length - h] = a[i];
				}
			}
			
			Item[] s = shuffle(r);
			r = s;
			
		}

		@Override
		public boolean hasNext() {

			return i < r.length;
		}

		@Override
		public Item next() {
			Item n = r[i];
			i++;
			return n;
		}

	}

	public static void main(String[] args) {
		RandomQueue<String> q = new RandomQueue<String>();
		for (int i = 0; i < 20; i++) {
			q.enqueue(i + "");
		}

		for (String s : q) {
			System.out.println(s);
		}
	}
}
